#include <vector>
#include <unordered_map>

using namespace std;

// 返回无序数组中累加和为给定值的子数组个数
// 测试链接 : https://leetcode.cn/problems/subarray-sum-equals-k/

class Solution 
{
public:
    int subarraySum(vector<int>& nums, int k) 
    {
        unordered_map<int, int> m;
        m[0] = 1; // 0 这个前缀和，在没有任何数字的时候，已经有 1 次了
        int sum = 0, ret = 0;
        for(int x : nums)
        {
            sum += x; // sum : 0 ... i 的前缀和
            if(m.count(sum - k)) ret += m[sum - k];
            ++m[sum];
        }
        return ret;
    }
};